Nearly all forms of electronic communication and storage systems use error-correcting codes. Error correcting codes compensate for the intrinsic unreliability of information transfer in these systems by introducing redundancy into the data stream. The mathematical foundations of error correcting were established by Shannon. Shannon developed the mathematical concept of the channel in which distortion of signals in communications systems is modeled as a random process. The most fundamental result of Shannon is the Noisy channel theorem, which defines for the channel a capacity, a quantity that specifies the maximum rate at which information can be reliably delivered through the channel. Reliable transmission at rates approaching capacity requires the use of error correcting codes. Thus, error-correcting codes are designed to achieve sufficient reliability while approaching capacity as closely as possible. The complexity of implementing the error correcting code is an additional factor that always comes into play in practical applications of error correcting codes. Recent advances in error correcting coding systems resulting from the invention of turbo codes and the subsequent rediscovery and development of low-density parity-check (LDPC) codes offer coding systems of feasible complexity that can approach Shannon's capacity quite closely.
LDPC codes are well represented by bipartite graphs, often called Tanner graphs, see FIG. 1 diagram 100, in which one set of nodes, the variable nodes 102, corresponds to bits of the codeword and the other set of nodes, the constraint nodes 106, sometimes called check nodes, correspond to the set of parity-check constraints which define the code. Edges 104 in the graph connect variable nodes to constraint nodes. A variable node and a constraint node are said to be neighbors if they are connected by an edge in the graph. One typically assumes that a pair of nodes is connected by at most one edge. LDPC codes can equivalently be represented using the parity check matrix. FIG. 2 presents an example where the indicated vector x 204 is a codeword if and only if Hx=0, where H 202 is a parity check matrix.
To each variable node is associated one bit of the codeword. In some cases some of these bits might be punctured or known. Punctured bits may be desirable in certain code structures and, in liftings (see below), both punctured and known bits can be used to achieve block lengths that are not multiples of the lifting. Punctured bits and known bits are excluded from the transmitted codeword.
A bit sequence associated one-to-one with the variable node sequence is a codeword of the code if and only if, for each constraint node, the bits neighboring the constraint (via their association with variable nodes) sum to zero modulo two, i.e., they comprise an even number of ones.
The decoders and decoding algorithms used to decode LDPC codewords operate by exchanging messages within the graph along the edges and updating these messages by performing computations at the nodes based on the incoming messages. Such algorithms will be generally referred to as message passing algorithms. Each variable node in the graph is initially provided with a soft bit, termed a received value, that indicates an estimate of the associated bit's value as determined by observations from, e.g., the communications channel. Ideally, the estimates for separate bits are statistically independent. This ideal can be, and often is, violated in practice.
The number of edges attached to a node, i.e., a variable node or constraint node, is referred to as the degree of the node. A regular graph or code is one for which all variable nodes have the same degree, j say, and all constraint nodes have the same degree, k say. In this case we say that the code is a (j,k) regular code. These were the codes considered originally by Gallager (1961). In contrast to a “regular” code, an irregular code has constraint nodes and/or variable nodes of differing degrees. For example, some variable nodes may be of degree 4, others of degree 3 and still others of degree 2.
While irregular codes can be more complicated to represent and/or implement, it has been shown that irregular LDPC codes can provide superior error correction/detection performance when compared to regular LDPC codes.
While implementation of LDPC encoders and decoders using multiple parallel processing elements to process sets of data as part of an encoding or decoding operation have proven both useful and reliable, in known implementations the number of parallel processing elements used in a decoder are normally the same as the number of parallel processing elements used in the encoder. Thus, in a system with multiple devices, e.g., a centralized device such as base station and/or satellite, which interacts with multiple mobile devices, the LDPC encoders and decoders in each of the devices in the system would normally have the same level of parallelism.
Given that the centralized device services multiple mobile devices, assuming real time operation and the same level of parallelism within the encoder/decoder, the centralized device will have to operate at a rate many times faster than the individual devices to keep up with the encoding/decoding associated with the various mobile devices being serviced.
From an implementation standpoint, it would be beneficial if the level of parallelism in different LDPC encoder/decoders in a system could be different. Such an approach would allow the level of parallelism in the encoder and/or decoder in a particular device to be matched to the amount of data to be transmitted/received by the device. By minimizing the amount of parallelism in a particular device, implementation costs can be minimized.
Use of large codes, e.g., including many nodes, which correspond to large graph structures offer many advantages over smaller codes, e.g., including only a few nodes, in terms of error resiliency. To implement a large graph structure using a smaller graph, various permutations may be applied to copies of the smaller graph structure and the copies can be linked together to generate a larger graph structure. In encoding/decoding operations, such permutation operations may be implemented by a switching device, referred to herein as a permuter which applies a permutation operation on elements, e.g., bits to be encoded in the case of an encoding operation or messages in the case of a decoding operation, as they are passed between a memory and a vector processing unit which performs LDPC operations in parallel.
Unfortunately, many LDPC codes do not lend themselves to implementations which would allow multiple different levels of parallelism in an encoder and decoder. In addition, while a single simple permutation operation like a cyclic shift is suitable for implementing a permuter suitable for use with many LDPC codes which can be represented using a large graph generated from a smaller graph, such a single permutation operation does not lend itself to implementing LDPC codes which could be implemented using different levels of parallelism.
In view of the above discussion, it should be appreciated that there is a need for codes and methods and apparatus for implementing LDPC encoders/decoders in a manner which allow for different degrees of parallelism in different devices which use the same code, e.g., LDPC graph structure, to perform LDPC encoding and/or LPDC decoding operations. In addition, there is a need for a practical way of implementing such encoders/decoders, e.g., through the use of new and improved permuters which would allow devices to use relatively large codes which can be derived from smaller graphs, but which also allow for different levels of parallelism to be implemented in different devices.